package nowcoder;

import java.util.ArrayList;
import java.util.stream.Collectors;

public class PermutationString {
	
	public static void main(String[] args) {
		String test = "abc";
		System.out.println(Permutation(test));
	}
	
	public static ArrayList<String> Permutation(String str) {
		ArrayList<String> res = new ArrayList<>();
		
		char[] chars = str.toCharArray();
		boolean[] isVisited = new boolean[chars.length];
		StringBuilder single = new StringBuilder();
		getPermutations(res, isVisited, single, chars, 0);
		
		res.sort((String s1, String s2)->s1.compareTo(s2));
		res = (ArrayList<String>)res.stream().distinct().collect(Collectors.toList());
		
		return res;
    }

	private static void getPermutations(ArrayList<String> res, boolean[] isVisited, StringBuilder single, char[] chars, int level) {
		if(level == chars.length) {		
			res.add(new String(single));
		}
		for(int i = 0; i < chars.length; i++) {
			if(!isVisited[i]) {
				isVisited[i] = true;
				single.append(chars[i]);
				getPermutations(res, isVisited, single, chars, level + 1);
				single.deleteCharAt(single.length() - 1);
				isVisited[i] = false;
			}
		}
	}

}
